Понятия со словосочетанием «максимальная степень»
Связанные понятия
Вполне упорядоченное множество — линейно упорядоченное множество M такое, что в любом его непустом подмножестве есть минимальный элемент, другими словами, это фундированное множество с линейным порядком.
Задача изоморфизма порождённому подграфу является NP-полной задачей разрешимости в теории сложности и теории графов. Задача заключается в поиске данного графа как порождённого подграфа другого, большего графа.
Многокритериальная оптимизация, или программирование (англ. Multi-objective optimization) — это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.
Двойственность, или принцип двойственности, — принцип, по которому задачи оптимизации можно рассматривать с двух точек зрения, как прямую задачу или двойственную задачу. Решение двойственной задачи даёт нижнюю границу прямой задачи (при минимизации). Однако, в общем случае, значения целевых функций оптимальных решений прямой и двойственной задач не обязательно совпадают. Разница этих значений, если она наблюдается, называется разрывом двойственности. Для задач выпуклого программирования разрыв двойственности...
В теории графов под ациклической раскраской понимается (правильная) раскраска вершин, в которой любой двуцветный подграф не имеет циклов.
Подробнее: Ациклическая раскраска графа
Тотальная раскраска возникает естественным путём, поскольку она является простым смешением вершинной и рёберной раскрасок.
В теории графов граф сравнимости — это неориентированный граф, в котором пары элементов соединены ребром, если эти элементы сравнимы в некотором частичном порядке. Графы сравнимости также называют транзитивно-ориентируемыми графами, частично упорядочиваемыми графами и графами вложенности.
Направленное множество в математике — непустое множество A с заданным на нем рефлексивным транзитивным отношением ≤ (то есть предпорядком), обладающее дополнительным свойством: у любой пары элементов из A есть верхняя грань в A.
Целевая функция — вещественная или целочисленная функция нескольких переменных, подлежащая оптимизации (минимизации или максимизации) в целях решения некоторой оптимизационной задачи. Термин используется в математическом программировании, исследовании операций, линейном программировании, теории статистических решений и других областях математики в первую очередь прикладного характера, хотя целью оптимизации может быть и решение собственно математической задачи. Помимо целевой функции в задаче оптимизации...
Цель (кибернетика) — желаемое состояние кибернетической системы, достигаемое в управляемом процессе развития системы. Состояние системы, как и её траектория в пространстве состояний, оценивается с точки зрения их соответствия или несоответствия цели. Математически выражением такой оценки является целевая функция, целевой функционал или критерий качества системы, критерий оптимизации.
Фу́нкция поле́зности — функция, с помощью которой можно представить предпочтения на некотором множестве альтернатив. Функция полезности является очень удобным вспомогательным средством, которое открывает возможность использования теории оптимизации при решении задачи потребителя. Без использования функции полезности решение такой задачи с математической точки зрения может быть затруднительным. С другой стороны, не каждое предпочтение может быть представлено с помощью функции полезности. Тем не менее...
В теории графов вполне упорядочиваемый граф — это граф, вершины которого можно упорядочить так, что алгоритм жадной раскраски с этим упорядочением оптимально раскрашивает любой порождённый подграф заданного графа. Соответствующее упорядочение назывется совершенным. Вполне упорядочиваемые графы образуют подкласс совершенных графов и в это подкласс входят хордальные графы, графы сравнимости и дистанционно-наследуемые графы. Однако проверка, является ли граф вполне упорядочиваемым, есть NP-полная задача...
Ациклическая ориентация неориентированного графа — это назначение направлений каждому ребру (ориентация), при которой не образуется какого-либо ориентированного цикла, а потому такая ориентация превращает граф в направленный ациклический граф. Любой граф имеет ациклическую ориентацию.
Индифферентный граф — это неориентированный граф, построенный путём назначения вещественного числа каждой вершине и соединения двух вершин ребром, когда их числа отличаются не более чем на единицу. Индифферентные графы являются также графами пересечений множеств единичных отрезков или интервалов с определённым свойством вложения (никакой интервал не содержит какой-либо другой). Основываясь на этих двух типах интервальных представлений, эти графы называются также графами единичных отрезков или собственными...
Связное доминирующее множество и остовное дерево с максимальной листвой являются двумя тесно связанными структурами, определёнными на неориентированном графе.
В теории графов
доминирующее множество рёбер (или рёберное доминирующее множество) графа G = (V, E) — это подмножество D ⊆ E, такое, что любое ребро не из D смежно по меньшей мере одному ребру из D. На рисунках (a)–(d) приведены примеры доминирующих множеств рёбер (красные рёбра).
Ориентация неориентированного графа — это назначение направлений каждому ребру, что превращает исходный граф в ориентированный граф.
В теории графов полная раскраска — это противоположность гармонической раскраске в том смысле, что это раскраска вершин, в которой каждая пара цветов встречается по меньшей мере на одной паре смежных вершин. Эквивалентно, полная раскраска — это минимальная раскраска, в том смысле, что её нельзя преобразовать в правильную раскраску с меньшим числом цветов путём слияния двух цветов. Ахроматическое число ψ(G) графа G — это максимальное число цветов среди всех полных раскрасок графа G.
В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины (5 и более рёбер).
Подробнее: Совершенный граф
Неориентированный
граф G двойственно хордален, если гиперграф его максимальных клик является гипердеревом. Имя происходит из факта, что граф хордален тогда и только тогда, когда гиперграф его максимальных клик двойственен гипердереву. Первоначально эти графы были определены по максимальному соседству и имеют ряд различных описаний. В отличие от хордальных графов свойство двойственной хордальности не наследуется, то есть, порождённые подграфы двойственного хордального графа не обязательно двойственно...
Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H.
Риманова оптимизация — собирательное название техник для решения оптимизационных задач, заданных на римановых многообразиях.
Скалярное ранжирование — подход к решению многокритериальных задач принятия решений, когда множество показателей качества (критериев оптимальности) сводятся в один с помощью функции скаляризации — целевой функции задачи принятия решения.
Задача потребителя — формализованная модель потребительского выбора между различными наборами благ (альтернатив) при заданных ценах, основанная на принципе рациональности выбора потребителя исходя из своих предпочтений. Чаще всего предполагается, что предпочтения потребителя задаются функцией полезности. Решением задачи потребителя является функция (отображение) спроса.
Циклический ранг ориентированного графа — мера связности орграфа, предложенная Эгганом и Бучи. Это понятие интуитивно отражает, насколько близок орграф к направленному ациклическому графу (НАГ, en:DAG), когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n. Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой итерации регулярных языков. Циклический ранг нашёл применение...
В теории графов
паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.
Теорема Дилуорса в комбинаторике — утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств.
Усечённая регрессия (англ. Truncated regression) или регрессия с урезанной выборкой — модель регрессии в условиях, когда выборка осуществляется только из тех наблюдений, которые, которые удовлетворяют априорным ограничениям, которые обычно формулируются как ограничение снизу и (или) сверху зависимой переменной. Урезание выборки приводит к смещенности МНК -оценок, поэтому оцениваются такие модели с помощью метода максимального правдоподобия.
Полуопределённое программирование (en: Semidefinite programming, SDP) — это подраздел выпуклого программирования, которое занимается оптимизацией линейной целевой функции (целевая функция — это заданная пользователем функция, значение которой пользователь хочет минимизировать или максимизировать) на пересечении конусов положительно полуопределённых матриц с аффинным пространством.
Древесность неориентированного графа — это минимальное число лесов, на которые можно разложить рёбра. Эквивалентно это является минимальным числом остовных деревьев, которые необходимы для покрытия рёбер графа.
Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.
Инвариантная мера — в теории динамических систем мера, определённая в фазовом пространстве, связанная с динамической системой и не изменяющаяся с течением времени при эволюции состояния динамической системы в фазовом пространстве. Понятие инвариантной меры применяется при усреднении уравнений движения, в теории показателей Ляпунова, в теории метрической энтропии и вероятностных фрактальных размерностей.
В теории вероятностей случайная величина имеет дискретное равномерное распределение, если она принимает конечное число значений с равными вероятностями.
Подробнее: Дискретное равномерное распределение
Задача о наименьшей окружности или задача о минимальном покрывающем круге — задача о вычислении наименьшей окружности, содержащей все заданные точки из множества на евклидовой плоскости.
Задача гамильтонова дополнения — это задача нахождения минимального числа рёбер, которое нужно добавить в граф, чтобы он стал гамильтоновым.
Подробнее: Гамильтоново дополнение
В теории динамических систем, энтропия динамической системы — число, выражающее степень хаотичности её траекторий. Различают метрическую энтропию, описывающую хаотичность динамики в системе с инвариантной мерой для случайного выбора начального условия по этой мере, и топологическую энтропию, описывающую хаотичность динамики без предположения о законе выбора начальной точки.
Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связны. Две вершины s и t любого графа сильно связны, если существует ориентированный путь из s в t и ориентированный путь из t в s.
Подробнее: Компонента сильной связности в орграфе
Топологическая энтропия — в теории динамических систем неотрицательное вещественное число, которое является мерой сложности системы.
В комбинаторной оптимизации под линейной задачей о назначениях на узкие места (linear bottleneck assignment problem, LBAP) понимается задача, похожая на задачу о назначениях.
Подробнее: Линейная задача о назначениях в узких местах
Вырожденность известна также под именем k-ядерное число, ширина и зацепление, и, по существу, это то же самое, что и число раскраски или число Секереша — Вилфа. k-Вырожденные графы называются также k-индуктивными графами. Вырожденность графа может быть вычислена за линейное время с помощью алгоритма, который последовательно удаляет вершины с минимальной степенью. Компонента связности, оставшаяся после удаления всех вершин со степенью , меньшей k, называется k-ядром графа, и вырожденность графа равна...
Метод внутренней точки — это метод позволяющий решать задачи выпуклой оптимизации с условиями, заданными в виде неравенств, сводя исходную задачу к задаче выпуклой оптимизации.
Сходи́мость по ме́ре (по вероя́тности) в функциональном анализе, теории вероятностей и смежных дисциплинах — это вид сходимости измеримых функций (случайных величин), заданных на пространстве с мерой (вероятностном пространстве).
Интервальная размерность графа — это минимальная размерность, в которой заданный граф может быть представлен в виде графа пересечений гиперпрямоугольников (то есть многомерных прямоугольных параллелепипедов) с параллельными осям рёбрами. То есть должно существовать один-к-одному соответствие между вершинами графа и множеством гиперпрямоугольников, таких, что прямоугольники пересекаются тогда и только тогда, когда существует ребро, соединяющее соответствующие вершины.
Центра́льные преде́льные теоре́мы (Ц. П. Т.) — класс теорем в теории вероятностей, утверждающих, что сумма достаточно большого количества слабо зависимых случайных величин, имеющих примерно одинаковые масштабы (ни одно из слагаемых не доминирует, не вносит в сумму определяющего вклада), имеет распределение, близкое к нормальному.
Подробнее: Центральная предельная теорема
Конгруэнция — отношение эквивалентности на алгебраической системе, сохраняющееся при основных операциях. Понятие играет важную роль в универсальной алгебре: всякая конгруэнция порождает соответствующую факторсистему — разбиение исходной алгебраической системы на классы эквивалентности по отношению к конгруэнции.